import jdk.nashorn.internal.runtime.ListAdapter;
import netscape.security.UserTarget;

import java.util.*;

public class LeetCode1743 {

    public static void main(String[] args) {
        int[][] adjacentPairs = {{2, 1}, {3, 4}, {3, 2}};

        Arrays.stream(restoreArray1(adjacentPairs)).forEach(System.out::println);
    }

    public static int[] restoreArray(int[][] adjacentPairs) {
        int m = adjacentPairs.length, n = m + 1;
        Map<Integer, Integer> cnts = new HashMap<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] adjacentPair : adjacentPairs) {
            int a = adjacentPair[0], b = adjacentPair[1];
            cnts.put(a, cnts.getOrDefault(a, 0) + 1);
            cnts.put(b, cnts.getOrDefault(b, 0) + 1);
            List<Integer> aList = map.getOrDefault(a, new ArrayList<>());
            aList.add(b);
            map.put(a, aList);
            List<Integer> bList = map.getOrDefault(b, new ArrayList<>());
            bList.add(a);
            map.put(b, bList);
        }
        int start = -1;
        for (int i : cnts.keySet()) {
            if (cnts.get(i) == 1) {
                start = i;
                break;
            }
        }
        int[] ans = new int[n];
        ans[0] = start;
        ans[1] = map.get(start).get(0);
        for (int i = 2; i < n; i++) {
            int x = ans[i - 1];
            List<Integer> list = map.get(x);
            for (int j : list) {
                if (j != ans[i - 2]) {
                    ans[i] = j;
                }
            }
        }
        return ans;
    }

    public static int[] restoreArray1(int[][] adjacentPairs) {
        int N = (int) 1e6+10;
        int[] q = new int[N];
        int m = adjacentPairs.length, n = m + 1;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] adjacentPair : adjacentPairs) {
            int a = adjacentPair[0], b = adjacentPair[1];
            List<Integer> aList = map.getOrDefault(a, new ArrayList<>());
            aList.add(b);
            map.put(a, aList);
            List<Integer> bList = map.getOrDefault(b, new ArrayList<>());
            bList.add(a);
            map.put(b, bList);
        }
        int l = N / 2, r = l + 1;
        int std = adjacentPairs[0][0];
        List<Integer> list = map.get(std);
        q[l--] = std;
        q[r++] = list.get(0);
        if (list.size() > 1) {
            q[l--] = list.get(1);
        }
        while ((r - 1) - (l + 1) + 1 < n) {
            List<Integer> aList = map.get(q[l + 1]);
            int j = l;
            for(int i : aList) {
                if (i != q[l + 2]) {
                    q[j--] = i;
                }
            }
            l = j;

            List<Integer> bList = map.get(q[r - 1]);
            j = r;
            for (int i : bList) {
                if (i != q[r - 2]) {
                    q[j++] = i;
                }
            }
            r = j;
        }
        int[] ans = new int[n];
        for (int i = l + 1, idx = 0; idx < n; i++, idx++) {
            ans[idx] = q[i];
        }
        return ans;
    }
}
